|
In mathematics, for positive integers ''k'' and ''s'', a vectorial addition chain is a sequence ''V'' of ''k''-dimensional vectors of nonnegative integers ''v''''i'' for −''k'' + 1 ≤ ''i'' ≤ ''s'' together with a sequence ''w'', such that :''v''-k+1 = () :''v''-k+2 = () ::: . ::: . : ''v''0 = () : ''v''i =''v''j+''v''r for all 1≤i≤s with -k+1≤j,r≤i-1 : ''v''s = () : ''w'' = (''w''1,...''w''s), ''w''i=(j,r). For example, a vectorial addition chain for () is :''V''=((),(),(),(),(),(),(),(),(),(),(),()) :''w''=((-2,-1),(1,1),(2,2),(-2,3),(4,4),(1,5),(0,6),(7,7),(0,8)) Vectorial addition chains are well suited to perform multi-exponentiation: :Input: Elements ''x''''0'',...,''x''''k-1'' of an abelian group ''G'' and a vectorial addition chain of dimension ''k'' computing () :Output:The element ''x''''0''''n''''0''...''x''''k-1''''n''''r-1'' :# for ''i'' =''-k''+1 to 0 do ''y''''i'' ''x''''i+k-1'' :# for ''i'' = 1 to ''s'' do ''y''''i'' ''y''''j''×''y''''r'' :#return ''y''''s'' ==Addition sequence== An addition sequence for the set of integer ''S ='' is an addition chain ''v'' that contains every element of ''S''. For example, an addition sequence computing : is :(1,2,4,8,10,11,18,36,47,55,91,109,117,226,343,434,489,499). It's possible to find addition sequence from vectorial addition chains and vice versa, so they are in a sense dual.〔Cohen, H., Frey, G. (editors): Handbook of elliptic and hyperelliptic curve cryptography. Discrete Math. Appl., Chapman & Hall/CRC (2006)〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Vectorial addition chain」の詳細全文を読む スポンサード リンク
|